package com.javabasic.algorithm.leetcode;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/6/8 00:02
 * @link [875. 爱吃香蕉的珂珂 - 力扣（LeetCode）](https://leetcode.cn/problems/koko-eating-bananas/)
 */
public class KokoEatingBananas {


    public int minEatingSpeed(int[] piles, int h) {
        int len = piles.length;

        if (len == 1 && h > piles[0]) {
            return 1;
        }

        int right = 0;
        int left = 0;

        for (int i = 0; i < len; i++) {
            if (right < piles[i]) {
                right = piles[i];
            }
        }

        /**
         * 二分法求下界
         */
        int mid;
        while (left < right) {
            mid = left + ((right-left)>>1);
            if (satisfyTheCondition(piles, len, mid, h)) {
                right = mid;
            } else {
                left = mid+1;
            }
        }
        return left;

    }

    private boolean satisfyTheCondition(int[] piles, int len, int rate, int h) {
        for (int i = 0; i < len; i++) {
            if (piles[i]%rate == 0) {
                h -= piles[i]/rate;
            } else  {
                h -= (piles[i]/rate + 1);
            }
        }
        return h >= 0;
    }
}
